package work.algorithm.image01;

import java.util.Arrays;

/**
 * 图像渲染问题
 * https://leetcode-cn.com/problems/flood-fill/solution/tu-xiang-xuan-ran-by-leetcode-solution/
 * 深度优先搜索
 * Depth-First-Search
 * DFS
 */
public class DFS01 {

    // dx和dy对应四个方向的位置
    int[] dx = {1, 0, 0, -1};
    int[] dy = {0, 1, -1, 0};

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int currColor = image[sr][sc];
        if (currColor != newColor) {
            dfs(image, sr, sc, currColor, newColor);
        }
        return image;
    }

    public void dfs(int[][] image, int x, int y, int color, int newColor) {
        if (image[x][y] == color) {
            image[x][y] = newColor;
            for (int i = 0; i < 4; i++) {
                // 往相邻的四个方向移动一个位置
                int mx = x + dx[i], my = y + dy[i];
                if (mx >= 0 && mx < image.length && my >= 0 && my < image[0].length) {
                    dfs(image, mx, my, color, newColor);
                }
            }
        }
    }


    public static void main(String[] args) {
        // 创建二维数组
        int[][] image  = {
            {1,1,1},
            {1,1,0},
            {1,0,1}
        };
        DFS01 dfs01 = new DFS01();
        int[][] newImage = dfs01.floodFill(image,1,1,2);
        System.out.println(Arrays.deepToString(newImage));

    }
}
